Typical ideas for coming up with solutions in competitive programming - NISHIO Hirokazu's Scrapbox (Auto-translated from Japanese)

Typical ideas for coming up with solutions in competitive programming

Typical ideas for coming up with solutions in competitive programming | Algorithmic Logic

There is quite a bit of overlap with what was being verbalized to put Power of Attribution on.

Think in terms of input constraints

Small constraint problem

Constraints with N around 8

Constraints with N around 10~20

Constraints with N around 30~40

Constraints with N around 50 O(N^4) OK

Constraints with N around 300~500

Constraints with N around 1000

Take it apart and think about it.

Notice the small constants.

Fix one variable

Fix the middle of three things

Half of the queue

divide into X and Y

Note the invariants of the operation.

focus on the even and odd

even and odd cases

independent of the order of operations

time reversal (physics)

Undoable operations

Cumulative product from left to right

Addition of isoperimetric sequences focuses on the difference

Composition of interval inversion is XOR

have an after-event

Binary search for k-th number

XOR is addition without carryover

XOR can be split by digit

45 degree rotation

Minimize difference is median

Typical graphs for consideration

Tree is a two-part graph

Diameter of tree

Maximization with bisection search.

Greed from those with fewer options.

Bipartite graph of two-dimensional coordinates

Make the order a directed graph

Extreme values of convex functions are tristimulus searches

Shakudori method for monotonic increase

The equi-proportion sequence focuses on the remainder

N-decimal numbers focus on the remainder.

Bracketed rows are up and down

Typical ideas for coming up with solutions in competitive programming to review the issues mentioned.

---

This page is auto-translated from /nishio/競技プログラミングで解法を思いつくための典型的な考え方 using DeepL. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at @nishio_en. I'm very happy to spread my thought to non-Japanese readers.